﻿// 1007train02.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <algorithm>
#include <limits>
#include <numeric>
#include <iomanip>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <deque>

using namespace std;

int candy(vector<int>& arr) {
    // write code here
    int v_size = arr.size();
    vector<int>result(v_size, 1);

    //正序扫一遍
    for (int i = 1; i < v_size; i++)
    {
        if (arr[i] > arr[i - 1])
        {
            result[i] = result[i-1]+1;
        }
    }
    //逆序扫一遍
    for (int i = v_size - 2; i >= 0; i--)
    {
        if (arr[i] > arr[i + 1] && result[i] <= result[i + 1])
        {
            result[i] = result[i + 1] + 1;
        }

    }

    int sum = 0;
    for (auto& num : result)
    {
        sum += num;
        //cout << num << ' ';
    }
    return sum;

    //
}


class Solution01 {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param matrix int整型vector<vector<>>
     * @return int整型vector
     */
    void backTrack(vector<vector<int>>& matrix,
        int left, int right, int top, int bottom
    )
    {
        //top行 left到right
        for (int c = left; c <= right; c++)
        {
            if (int(result.size()) == target_size) return;
            result.push_back(matrix[top][c]);
        }
        //right列 top+1到bottom
        for (int r = top + 1; r <= bottom; r++)
        {
            if (int(result.size()) == target_size) return;
            result.push_back(matrix[r][right]);
        }
        //bottom行 right-1到left
        for (int c = right - 1; c >= left; c--)
        {
            if (int(result.size()) == target_size) return;
            result.push_back(matrix[bottom][c]);
        }
        //left列 bottom-1到top+1
        for (int r = bottom - 1; r >= top + 1; r--)
        {
            if (int(result.size()) == target_size) return;
            result.push_back(matrix[r][left]);
        }
        if (left + 1 <= right - 1 && top + 1 <= bottom - 1)
        {
            backTrack(matrix, left + 1, right - 1, top + 1, bottom - 1);
        }
    }
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        // write code here
        if (matrix.empty()) return result;
        row_size = matrix.size();
        col_size = matrix[0].size();
        target_size = row_size * col_size;
        backTrack(matrix, 0, col_size - 1, 0, row_size - 1);
        return result;
    }
private:
    int row_size = 0, col_size = 0;
    int target_size = 0;
    vector<int>result;
};

class Solution02 {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 比较版本号
     * @param version1 string字符串
     * @param version2 string字符串
     * @return int整型
     */
    vector<int>getVec(string& str)
    {
        stringstream oh_sstream(str);
        vector<int>res;
        string token;
        while (getline(oh_sstream, token, '.'))
        {
            res.push_back(stoi(token));
        }
        return res;
    }
    void resizeVec(vector<int>& vec, int target_size)
    {
        while (vec.size() < target_size)
        {
            vec.push_back(0);
        }
    }
    int compare(string version1, string version2) {
        // write code here
        vector<int>vec_1, vec_2;
        vec_1 = getVec(version1);
        vec_2 = getVec(version2);
        int size_1 = vec_1.size(), size_2 = vec_2.size();
        int max_size = max(size_1, size_2);
        resizeVec(vec_1, max_size);
        resizeVec(vec_2, max_size);
        for (int i = 0; i < max_size; i++)
        {
            if (vec_1[i] == vec_2[i]) continue;
            if (vec_1[i] > vec_2[i]) return 1;
            if (vec_1[i] < vec_2[i]) return -1;

        }
        return 0;
    }
};


bool canJump(vector<int>& nums) {
    int index = 0;
    int max_right_pos = nums[0];

    int v_size = nums.size();

    while (index != v_size - 1)
    {
        bool is_jump = false;
        if (max_right_pos >= v_size - 1)
        {
            return true;
        }
        int curr = index;
        int curr_right = max_right_pos;

        for (int i = curr; i <= min(curr_right,v_size-1); i++)
        {
            if (i + nums[i] > curr_right)
            {
                is_jump = true;
                curr = i;
                curr_right = i + nums[i];
            }
        }
        if (is_jump)
        {
            index = curr;
            max_right_pos = curr_right;
            continue;
        }
        return false;
        //
    }
    return true;
    //
}

int jump(vector<int>& nums) {
    int index = 0;
    int max_right = nums[0];
    int v_size = nums.size();
    if (index == v_size - 1)
        return 0;
    if (max_right >= v_size - 1)
        return 1;

    int step = 0;
    while (index < v_size - 1)
    {
        if (max_right >= v_size - 1)
        {
            step++;
            break;
        }

        int curr = index, curr_right = max_right;
        for (int i = curr + 1; i <= min(max_right, v_size - 1); i++)
        {
            if (i + nums[i] > curr_right)
            {
                curr = i;
                curr_right = i + nums[i];
            }
        }
        index = curr;
        max_right = curr_right;
        step++;
        //while---
    }
    return step;
    //---
}


/*
 输入描述
首行输入两个正整数 n, m
接下来 n 行，每行输入 2 个整数快递信息，
格式为：客户 id 快递送到客户手中的距离 distance
再接下来 m 行，每行输入 3 个整数客户之间的距离信息，
格式为：客户 id1 客户 id2 两个客户之间的距离 distance
在行末有换行符。数据保证输入均为以换行符隔开的整数。

输出描述
最短路径距离，如无法找到则输出 -1

输入
2 1
1 1000
2 1200
1 2 300
输出
2500

输入
5 1
5 1000
9 1200
17 300
132 700
500 2300
5 9 400
输出
9200
 */
class Solution03
{
public:
    int compute(int N)
    {
        if (track_v.empty()) return 0;

        int cost = 0;
        int track_size = track_v.size();
        cost += cost_grid[0][track_v[0]];
        if (track_size ==1)
        {
            return cost;
        }
        for (int i=0; i<track_size-1; i++)
        {
            int curr = track_v[i];
            int next = track_v[i + 1];
            cost += cost_grid[curr][next];
        }
        if (track_size == N)
        {
            cost += cost_grid[track_v.back()][0];
        }
        return cost;
    }

    void backTrack(vector<bool>&checked, int N)
    {
        if (compute(N) > min_cost) return;

        int track_size = track_v.size();
        if (track_size == N)
        {
            int curr_cost = compute(N);
            min_cost = min(curr_cost, min_cost);
            return;
        }

        for (int i=1; i<=N; i++)
        {
            if (checked[i]) continue;
            track_v.push_back(i);
            checked[i] = true;
            backTrack(checked, N);
            track_v.pop_back();
            checked[i] = false;
        }
	    //
    }

    Solution03(vector<vector<int>>&origin_v, int N)
    {
        cost_grid = vector<vector<int>>(N+1, vector<int>(N+1,INT_MAX));
        index_map[0] = 0;
        for (int i=1; i<=N; i++)
        {
            int index = origin_v[i - 1][1];
            index_map[index] = i;
        }
        int origin_size = origin_v.size();

        for (int i=0; i<origin_size; i++)
        {
            int index0 = origin_v[i][0];
            int index1 = origin_v[i][1];
            int val = origin_v[i][2];

            index0 = index_map[index0];
            index1 = index_map[index1];

            cost_grid[index0][index1] = val;
            cost_grid[index1][index0] = val;
        }
        //对角线全0
        for (int i=0; i<=N; i++)
        {
            cost_grid[i][i] = 0;
        }

        //floyd算法
        for (int k=0; k<=N; k++)
        {
	        for (int i=0; i<=N; i++)
	        {
		        for (int j=0; j<=N; j++)
		        {
                    if (cost_grid[i][k]==INT_MAX || cost_grid[k][j]==INT_MAX)
                    {
                        continue;
                    }
                    int new_val = cost_grid[i][k] + cost_grid[k][j];
                    cost_grid[i][j] = min(new_val, cost_grid[i][j]);
		        }
	        }
        }

        vector<bool>checked(N+1,false);

        backTrack(checked, N);

        cout << min_cost;
	    //Solu
    }
private:
    int min_cost = INT_MAX;
    vector<int>track_v;
    vector<vector<int>>cost_grid;
    unordered_map<int, int>index_map;
};

int main()
{
	{
/*
5 1
5 1000
9 1200
17 300
132 700
500 2300
5 9 400
*/
        int N, M;
        cin >> N >> M;
        int v_size = N + M;
        vector<vector<int>>origin_v(v_size, vector<int>(3));

        for (int i=0; i<N; i++)
        {
            origin_v[i][0] = 0;
            cin >> origin_v[i][1] >> origin_v[i][2];
        }
        for (int i=N; i<v_size; i++)
        {
            cin >> origin_v[i][0] >> origin_v[i][1] >> origin_v[i][2];
        }

        Solution03 solu(origin_v, N);

        return 0;
	}
	{
        vector<int>nums = { 2,3,0,1,4 };
        jump(nums);
        return 0;
	}
	{
        //2,3,1,1,4
        //3,2,1,0,4
        vector<int>nums = { 3,2,1,0,4 };
        cout << canJump(nums);
        return 0;
	}
	{
        string version_1 = "1.0.1", version_2 = "1";
        Solution02 solu;
        solu.compare(version_1, version_2);

        return 0;
	}
    //vector<int>num_vec = {1,4,2,7,9};
    //candy(num_vec);
    vector<vector<int>>matrix = {
		{1,2,3},{4,5,6},{7,8,9}
    };
    Solution01 solu;
    solu.spiralOrder(matrix);

    return 0;
}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
